package _06_动态规划;

import java.util.Stack;

public class _42_接雨水 {

    // 动态规划
    public int trap(int[] height) {
        int len = height.length;
        int[] leftMax = new int[len];
        int[] rightMax = new int[len];
        for (int i = 1; i < len; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        for (int i = len - 2; i > 0; i++) {

        }
        return 0;
    }

    // 只要找到当前槽位左边的最大值，右边的最小值，并且选取最大值中的最小值
    public int trap1(int[] height) {
        int result = 0;
        int len = height.length;
        // 单调栈解法
        Stack<Integer> rightStack = new Stack<>();
        for (int i = len - 1; i > 0; i--) {
            if (!rightStack.isEmpty() && height[i] < rightStack.peek()) continue;
            rightStack.push(height[i]);
        }
        // 右栈
        Stack<Integer> leftStack = new Stack<>();
        leftStack.push(height[0]);
        int end = len - 1;
        for (int i = 1; i < end; i++) {
            // 维护右栈
            if (height[i] == rightStack.peek()) {
                rightStack.pop();
            }
            result += Math.max(0, Math.min(leftStack.peek(), rightStack.peek()) - height[i]);
            // 维护左右栈
            if (height[i] > leftStack.peek()) {
                leftStack.push(height[i]);
            }
        }
        return result;
    }

}
